package cn.wit.testalgorithms;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 496.下一个最大元素
 * 优化算法：递减栈法
 * 算法复杂度：相当于双重for循环的最好情况，只有O(n)
 * 待理解
 * @author 16604
 *
 */

public class DemoOptimisticNextMaxNumber {
	public static void main(String[] args) {
		int[] nums1 = { 4, 1, 2 };
		int[] nums2 = { 1, 3, 4, 2 };

		System.out.println(Arrays.toString(nextGreaterElement(nums1, nums2)));
		
	}
	public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
		
		  Stack<Integer> stack = new Stack<Integer>();
	        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	        for (int i : nums2) {
	            if (stack.isEmpty()) {
	                stack.push(i);
	                continue;
	            }
	            if (i <= stack.peek()) stack.push(i);
	            else {
	                while (!stack.isEmpty() && i > stack.peek()) {
	                     map.put(stack.pop(), i);	//一定要记录相应的键值
	                }
	                stack.push(i);
	            }
	        }
	       

	        // 没有下个更大的元素没有放入map中

	        int[] res = new int[nums1.length];
	        
	        
	        //解释一下getOrDefault方法，当map集合里面有这个值的时候，就只用这个值，如果没有，就使用我们提供的-1
	        for (int i = 0; i < nums1.length; i ++) {
	            res[i] = map.getOrDefault(nums1[i], -1);
	        }

	        return res;
	}

}
